﻿<!DOCTYPE html>
<html>

<head>
  <meta charset="utf-8">
  <meta name="viewport" content="width=device-width, initial-scale=1.0">
  <title>MPI实现RS纠删码.md</title>
  <link rel="stylesheet" href="https://stackedit.io/style.css" />
</head>

<body class="stackedit">
  <div class="stackedit__html"><h1 id="mpi实现rs纠删码">MPI实现RS纠删码</h1>
<p><strong>计试61 张翀 2140506063</strong></p>
<h2 id="题目">题目</h2>
<p>使用MPI实现RS纠删码。</p>
<blockquote>
<p>RS code的编解码定义如下：</p>
<ul>
<li>编码：给定n个数据块（Data block）D1、D2……Dn，和一个正整数m，RS根据n个数据块生成m个编码块（Code block），C1、C2……Cm。</li>
<li>解码：对于任意的n和m，从n个原始数据块和m个编码块中任取n块就能解码出原始数据，即RS最多容忍m个数据块或者编码块同时丢失。</li>
</ul>
</blockquote>
<p>简而言之，就是针对n位的数据，建立m行n列的编码矩阵，计算这段数据的m位编码，和数据合并成为这段数据的(n+m)位纠删码。在这段数据中有n位保证正确的位置和值时，无论是原始数据还是编码，都可以求解出原始编码。</p>
<p>此处为了简单，要求<code>n=m</code>，编码矩阵使用n维的范德蒙矩阵；而且要求矩阵维度数是进程数的整倍数。</p>
<h2 id="思路">思路</h2>
<p>实验原理参考<a href="https://blog.csdn.net/qq_29110265/article/details/86519879">博客</a>，实际上解码过程是对一个线性方程组的求解。本次实验通过MPI实现了高斯消元法，通过求解线性方程组来重新解码。</p>
<p>高斯消元法的原理：系数矩阵首先变上三角，然后变对角线。在变上三角的时候，每次选取绝对值最大的列主元进行整列的消除。</p>

<div class="stackedit__html">
</div>

<h2 id="代码">代码</h2>
<p>在这里，我们主要使用<code>Scatter-Gather</code>和<code>BCast</code>两条指令做数据的分发和接收。</p>
<h3 id="scatter-gather">Scatter-Gather</h3>
<p>在这次实验的程序设计中，经常需要把计算任务<strong>全覆盖、不重叠地</strong>分给各个进程做，所以用<code>Scatter</code>分发，用<code>Gather</code>接收比较合适。<br>
以下是<code>MPI_Scatter</code>的函数原型：</p>
<pre class=" language-cpp"><code class="prism  language-cpp"><span class="token keyword">int</span> <span class="token function">MPI_Scatter</span><span class="token punctuation">(</span>
    <span class="token keyword">void</span><span class="token operator">*</span> send_data<span class="token punctuation">,</span>
    <span class="token keyword">int</span> send_count<span class="token punctuation">,</span>
    MPI_Datatype send_datatype<span class="token punctuation">,</span>
    <span class="token keyword">void</span><span class="token operator">*</span> recv_data<span class="token punctuation">,</span>
    <span class="token keyword">int</span> recv_count<span class="token punctuation">,</span>
    MPI_Datatype recv_datatype<span class="token punctuation">,</span>
    <span class="token keyword">int</span> root<span class="token punctuation">,</span>
    MPI_Comm communicator
<span class="token punctuation">)</span><span class="token punctuation">;</span>
</code></pre>
<p>对于需要分发的消息，需要指定源数据、数据类型和广播消息的进程，并指定发送给每个进程的数据量，以及每个进程接收数据的位置指针。执行这条命令之后，按照进程号顺序，指定数据会分发给每一个进程。<br>
以下是<code>MPI_Gather</code>的函数原型：</p>
<pre class=" language-cpp"><code class="prism  language-cpp"><span class="token keyword">int</span> <span class="token function">MPI_Gather</span><span class="token punctuation">(</span>
    <span class="token keyword">void</span><span class="token operator">*</span> send_data<span class="token punctuation">,</span>
    <span class="token keyword">int</span> send_count<span class="token punctuation">,</span>
    MPI_Datatype send_datatype<span class="token punctuation">,</span>
    <span class="token keyword">void</span><span class="token operator">*</span> recv_data<span class="token punctuation">,</span>
    <span class="token keyword">int</span> recv_count<span class="token punctuation">,</span>
    MPI_Datatype recv_datatype<span class="token punctuation">,</span>
    <span class="token keyword">int</span> root<span class="token punctuation">,</span>
    MPI_Comm communicator
<span class="token punctuation">)</span>
</code></pre>
<p>参数基本相同，从部分数据变量中读取数据，按照进程号顺序被目标进程收集。<br>
注意：使用<code>Scatter</code>分配数据后，每个进程分配的部分矩阵具有完全相等的规模。<br>
另外，主进程也要参与数据分发。</p>
<h3 id="broadcast">Broadcast</h3>
<p>在这次实验的程序设计中，我们经常需要把一个完整的只读信息发给各个进程，所以用<code>BCast</code>分发比较合适。<br>
以下是<code>MPI_Bcast</code>的函数原型：</p>
<pre class=" language-cpp"><code class="prism  language-cpp"><span class="token keyword">int</span> <span class="token function">MPI_Bcast</span><span class="token punctuation">(</span>
    <span class="token keyword">void</span> <span class="token operator">*</span> data_p<span class="token punctuation">;</span>
    <span class="token keyword">int</span> count<span class="token punctuation">;</span>
    MPI_Datatype datatype<span class="token punctuation">;</span>
    <span class="token keyword">int</span> source_proc<span class="token punctuation">;</span>
    MPI_Comm comm<span class="token punctuation">;</span>
<span class="token punctuation">)</span><span class="token punctuation">;</span>
</code></pre>
<p><code>MPI_Bcast</code>要求所有进程保有同一个变量指针，然后从一个进程的对应位置复制数据，拷贝到其他进程。</p>
<h3 id="实际设计">实际设计</h3>
<p>代码在高斯消元法的如下环节并行：</p>
<ul>
<li>寻找列主元：每个进程负责检查一部分列元素，然后整合结果</li>
<li>消除（变上三角时）：每个进程负责一部分互减。每个进程传入一部分行，进行互减，减完后合并结果。</li>
<li>消除（变对角线时）：每个进程负责一部分互减。在实现时为了简单，采用了和上一步消除相同的方法，但实际上不需要传入整个的B矩阵行，只需要更新对应的列就可以了。传入整个的BG稍微有些浪费内存，这也是代码下一步优化的方向。</li>
</ul>
<p>几次并行的通信均选用<code>Scatter-Gather</code>，而辅助信息的广播使用<code>BCast</code>.</p>
<p>因为代码太长，所以不在报告中体现，可以参考随报告的附件。</p>
<h2 id="实验结果">实验结果</h2>
<p>使用如下命令编译并执行：<code>mpicxx main.cpp &amp;&amp; mpiexec -n num_processes ./a.out mat_dim</code>，执行可执行文件时带的两个参数分别是矩阵维度和使用的进程数。</p>

<div class="stackedit__html">
</div>

<h3 id="程序的正确性">程序的正确性</h3>
<p>因为较大的范德蒙矩阵的元素大小可以非常大，数据类型无法支持较大数的存储，所以无法进行位数较多的纠删码的实验。以下展示2位数据和8位数据的实验结果：</p>
<p>执行命令<code>mpicxx main.cpp &amp;&amp; mpiexec -n 2 ./a.out 2</code>，使用2个进程，产生2位数据并对其进行编码解码。</p>
<pre><code>A:
1       0
0       1
1       1
1       2
d:
3
4
e:
3
4
7
11
</code></pre>
<p>原始数据为[3 4]，编码后数据为[3 4 7 11].随机去除一半数位之后情况如下：</p>
<pre><code>B:
1       0
1       1
g:
3
7
</code></pre>
<p>经过高斯消元法求解，获得结果如下：</p>
<pre><code>B:
1       0
0       1
g:
3
4
</code></pre>
<p>数据已经被正确还原。</p>
<p>以下是8位数据的编码，丢失，还原过程，数据能够被正确还原：</p>
<pre><code>A:
1       0       0       0       0       0       0       0
0       1       0       0       0       0       0       0
0       0       1       0       0       0       0       0
0       0       0       1       0       0       0       0
0       0       0       0       1       0       0       0
0       0       0       0       0       1       0       0
0       0       0       0       0       0       1       0
0       0       0       0       0       0       0       1
1       1       1       1       1       1       1       1
1       2       3       4       5       6       7       8
1       4       9       16      25      36      49      64
1       8       27      64      125     216     343     512
1       16      81      256     625     1296    2401    4096
1       32      243     1024    3125    7776    16807   32768
1       64      729     4096    15625   46656   117649  262144
1       128     2187    16384   78125   279936  823543  2.09715e+06
d:
3
4
4
4
1
4
0
4
e:
3
4
4
4
1
4
0
4
24
100
544
3436
23608
170500
1.27038e+06
9.66128e+06
B:
1       0       0       0       0       0       0       0
0       0       1       0       0       0       0       0
0       0       0       1       0       0       0       0
0       0       0       0       1       0       0       0
0       0       0       0       0       1       0       0
0       0       0       0       0       0       0       1
1       1       1       1       1       1       1       1
1       4       9       16      25      36      49      64
g:
3
4
4
1
4
4
24
544
Reduce to up-right triangle begin
Reduce to up-right triangle end
B:
1       0       0       0       0       0       0       0
0       0       0       -2.4    -4.2    -6.4    -9      -12
0       0       0       0       -1.75   -2.66667        -3.75   -5
0       0       0       0       0       -1.52381        -2.14286        -2.85714
0       0       0       0       0       0       -1.40625        -1.875
0       0       0       0       0       0       0       1
0       0       -1.25   -3      -5.25   -8      -11.25  -15
0       4       9       16      25      36      49      64
g:
3
-87.4
-32.4167
-17.5238
-7.5
4
-114.25
541
Reduce to diagram begin
Initial bg in diagram
Bg:
1       0       0       0       0       0       0       0       3
0       0       0       -2.4    -4.2    -6.4    -9      -12     -87.4
0       0       0       0       -1.75   -2.66667        -3.75   -5      -32.4167
0       0       0       0       0       -1.52381        -2.14286        -2.85714        -17.5238
0       0       0       0       0       0       -1.40625        -1.875  -7.5
0       0       0       0       0       0       0       1       4
0       0       -1.25   -3      -5.25   -8      -11.25  -15     -114.25
0       4       9       16      25      36      49      64      541
Time: 0.0015676
Reduce to diagram end
B:
1       0       0       0       0       0       0       0
0       0       0       1       0       0       0       0
0       0       0       0       1       0       0       0
0       0       0       0       0       1       0       0
0       0       0       0       0       0       1       0
0       0       0       0       0       0       0       1
0       0       1       0       0       0       0       0
0       1       0       0       0       0       0       0
g:
3
4
1
4
-6.31594e-16
4
4
4
</code></pre>
<h3 id="程序的执行性能">程序的执行性能</h3>

<table>
<thead>
<tr>
<th align="center">线程数</th>
<th align="center">1</th>
<th align="center">2</th>
</tr>
</thead>
<tbody>
<tr>
<td align="center">2</td>
<td align="center">0.000371695</td>
<td align="center">0.000465631</td>
</tr>
<tr>
<td align="center">4</td>
<td align="center">0.000828505</td>
<td align="center">0.000927448</td>
</tr>
<tr>
<td align="center">6</td>
<td align="center">0.00101304</td>
<td align="center">0.00135946</td>
</tr>
<tr>
<td align="center">8</td>
<td align="center">0.00204182</td>
<td align="center">0.00223827</td>
</tr>
</tbody>
</table><p>在这种计算量较小的任务中，因为通信的任务量相对占比较大，所以2进程并行的时间加速比有限，甚至不如1进程串行的速度。尽管如此，在计算量较大的任务中，仍然能体现出并行的时间优势。</p>
</div>
</body>

</html>
